import common.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 98. 验证二叉搜索树  Validate Binary Search Tree
 * https://leetcode-cn.com/problems/validate-binary-search-tree/
 */
class ValidateBinarySearchTree {
    /**
     *      方法： 通过栈实现中序遍历
     *
     *      Args:
     *          root: Optional[TreeNode] - 二叉树的根节点
     *
     *      Returns:
     *          bool: 如果是有效的二叉搜索树则返回True，否则返回False
     *
     *      Time: O(n) - 其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)
     *
     *      Space: O(n)，其中 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需要额外的 O(n) 的空间
     */
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        double inorder = -Double.MAX_VALUE;
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.val <= inorder){
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }

    /**
     *      方法： 前序遍历递归
     *
     *      Args:
     *          root: Optional[TreeNode] - 二叉树的根节点
     *
     *      Returns:
     *          bool: 如果是有效的二叉搜索树则返回True，否则返回False
     *
     *      Time: O(n) - 其中n是二叉树的节点数，每个节点只被访问一次
     *
     *      Space: O(h) - 其中h是二叉树的高度，用于存储递归调用栈
     */
    public boolean isValidBST1(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long left, long right){
        if (node == null) return true;
        long x = node.val;
        return left < x && x < right && isValidBST(node.left, left, x) && isValidBST(node.right, x, right);
    }
}